package main

func minimumDeleteSum(s1 string, s2 string) int {
	dp := make([][]int, len(s1)+1)
	for i := 0; i <= len(s1); i++ {
		dp[i] = make([]int, len(s2)+1)
	}
	dp[0][0] = 0
	for i := 1; i <= len(s1); i++ {
		dp[i][0] = dp[i-1][0] + int(s1[i-1])
	}
	for i := 1; i <= len(s2); i++ {
		dp[0][i] = dp[0][i-1] + int(s2[i-1])
	}
	for i := 1; i <= len(s1); i++ {
		for j := 1; j <= len(s2); j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				temp1 := dp[i-1][j] + int(s1[i-1])
				temp2 := dp[i][j-1] + int(s2[j-1])
				if temp1 < temp2 {
					dp[i][j] = temp1
				} else {
					dp[i][j] = temp2
				}
			}
		}
	}
	return dp[len(s1)][len(s2)]
}

func main() {
	minimumDeleteSum("ab", "a")
}
